package org.chnxi.study.datastructrues.recursion;

/**
 * 解决8皇后的问题
 */
public class Queen8 {

    //先定义max表示一共有多少个皇后
    int max = 8;

    //定义一个数组，保存皇后最终放位置的结果
    int[] array = new int[max];

    //解法计数
    int count = 0;

    /**
     * 打印皇后的最终位置
     */
    void print(){
        System.out.print("第"+count+"种解法：");
        for (int i =0; i<array.length ; i++){
            System.out.print(array[i]+" ");
        }
        System.out.println("");
    }

    /**
     * 查看防止第N个皇后时，去检测该皇后是否和前面已经摆放的皇后冲突
     * @param n 表示第N个皇后
     * @return
     */
    boolean judge(int n){
        for(int i = 0 ; i < n;i++){
            //判断是否在同一列
            if(array[i] == array[n] ||
            //判断是否在同一斜线
            Math.abs(n-i) == Math.abs(array[n] - array[i])){
                return false;
            }
        }
        return true;
    }

    /**
     * 向棋盘上放置皇后
     * @param n
     */
    void check(int n){
        if(n == max){ //全部放完
            count++;
            print();
            return;
        }

        //依次放入，并判断是否冲突
        for (int i = 0 ; i< max ; i++){
            //先把当前这个皇后放在改行的第一列
            array[n] = i;
            //判断是否冲突
            if(judge(n)){
                //不冲突，放下一个皇后
                check(n+1);
            }else{
                //如果冲突，继续执行下一列，执行循环的i++，所以这里是空的
            }
        }
    }

    public static void main(String[] args) {
        Queen8 q = new Queen8();
        q.check(0);
    }
}
